UVa/10131 - Is bigger smarter?/10131.cpp

   1 #include<iostream>
   2 #include<algorithm>
   3 #include<vector>
   4 using namespace std;
   5 struct elefante{
   6   int w,a,i;
   7   elefante(int W, int A, int I) : w(W), a(A), i(I){}
   8   bool operator < (const elefante& x) const{
   9     return (w < x.w) || (w == x.w && a < x.a) ||
  10       (w == x.w && a == x.a && i < x.i);
  11   }
  12 };
  13 void print(const int &i,const vector<int> &p,const vector<elefante> &e){
  14   if(p[i]==-1){
  15     cout<<e[i].i<<endl;
  16   }else{
  17     print(p[i],p,e);
  18     cout<<e[i].i<<endl;
  19   }
  20 }
  21 int main(){
  22   int w, a;
  23   int cuenta=1;
  24   vector <elefante> e;
  25   while(cin >> w >> a){
  26     e.push_back(elefante(w,a,cuenta++));
  27   }
  28   sort(e.begin(),e.end());
  29   vector <int> A (e.size(),1),P(e.size(),-1);
  30   for(int i=1;i<e.size();++i){
  31     for(int j=0;j<i;++j){
  32       if(e[j].a>e[i].a && A[i]< A[j]+1){
  33         A[i]=A[j]+1;
  34         P[i]=j;
  35       }
  36     }
  37   }
  38   int maximo=A[0];
  39   int indexMax=0;
  40   for(int i=1;i<A.size();++i){
  41     if(A[i]>maximo){
  42       maximo=A[i];
  43       indexMax=i;
  44     }
  45   }
  46   cout<<maximo<<endl;
  47   print(indexMax,P,e);
  48   return 0;
  49 }